package com.hackerank.arrays;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

/**
 * Array Manipulation 数组操作
 * https://www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays
 * https://www.hackerrank.com/challenges/crush/problem
 *
 * 题目大意：中文不解释
 *
 * 解题思路：
 *
 * 利用前缀和概念
 *
 * 1、题目需要求出经过 q 次操作的最大值，所以可以考虑定义一个变量存放最大值
 * 2、在数组索引 a 和 b 之间所有的数加上数值 k ，灵活利用前缀和的概念，截止到 目前的第 q1 次查询，遍历到索引b1的位置遇到的最大值
 *      为 所有查询的 a < b1的k值和，减去 b < b1的k值和
 * 3、注意Java int 的最大值为 2 的 31次方（正数范围），应使用long
 * */
public class ArrayManipulation {
    static long arrayManipulation(int n, int[][] queries) {
        int len = queries.length;
        int[] sum = new int[n+1];
        for(int i=0;i<len;i++){
            int[] query = queries[i];//a = query[0],b = query[1],k = query[2]
            sum[query[0]] += query[2];
            if(query[1] < n)
                sum[query[1]+1] -= query[2];
        }
        long isum = 0,max = 0;
        for(int i=0;i<n+1;i++){
            isum += sum[i];
            if(max < isum)
                max = isum;
        }
        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader breader = new BufferedReader(new FileReader("d:/input04.txt"));
        String line = breader.readLine();
        String[] lines = line.split(" ");
        int n = Integer.parseInt(lines[0]);
        int qlen = Integer.parseInt(lines[1]);
        int[][] queries = new int[qlen][3];
        for(int i=0;i<qlen;i++){
            line = breader.readLine();
            if(line == null)
                break;
            lines = line.split(" ");
            int a = Integer.parseInt(lines[0]);
            int b = Integer.parseInt(lines[1]);
            int k = Integer.parseInt(lines[2]);
            queries[i][0] = a;
            queries[i][1] = b;
            queries[i][2] = k;
        }
        long max = arrayManipulation(n,queries);
        System.out.println(max);
    }
}